#include<stdio.h>
#include<malloc.h>
#include<string.h>

//3.1 九宫格结构体实现
#define MAXSIZE 3
#define ZERO 0
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int NODE[MAXSIZE][MAXSIZE];
typedef int STATUS;

typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE *next;       //领进节点
}NEIGHBORNODE,*NEIGHBOR;             //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】

typedef struct ANODE                 //节点类型
{
    NODE node;                       //节点
    NEIGHBOR adjacents;              //邻近节点
}ANYNODE;                            //节点类型【将ANODE重命名为ANYNODE】

typedef struct GRAPHNODE             //图的节点的存储类型
{
    ANYNODE node;                    //节点
    struct GRAPHNODE *next;          //其他节点
}GRAPHNODE,*GRAPH;                   //图类型【*GRAPH为指向GRAPHNODE的指针】

typedef struct NEIGHBORNODE *PATH;   //路径类型

typedef struct Paths                 //路径集合类型
{
    PATH path;                       //一条路径
    struct Paths *next;              //下一条路径
}Paths,*PATHS;                       //路径集合类型【*PATHS为指向PATH的指针】

typedef struct Paths *STACK;                //定义堆栈类型，实际上也是节点链表【相邻节点链表】

//3.2.2 通用赋值函数
void Set(NODE node1, NODE node2)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            node1[i][j] = node2[i][j];
        }
    }
}

//3.7.1 判断两个九宫格是否相同、赋值
STATUS equal(NODE node1, NODE node2)
{
    int i, j;
    STATUS flag = TRUE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node1[i][j] != node2[i][j])
            {
                flag = FALSE;
                return 0;
                break;
            }
        }
        if (flag == FALSE)   break;
    }
    return 1;
}

//3.7.2 显示九宫格
void PriNode(NODE node)
{
    int i, j;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)  printf("%5d", node[i][j]);
        printf("\n");
    }
    printf("****************\n");
}

void PriPath(PATH path)                     //显示路径
{
    while (path!= NULL)
    {
        PriNode(path->node);
        path = path->next;
    }
    printf("\n");
    //priNeighbors((NEIGHBOR)path);             //路径与兄弟节点集合形式相同
}

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br, NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b, pb;                                  //相邻节点
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    Set(b->node, node);             //【下面两行是类型为str时的情况，其他类比】
    b->next = NULL;
    if (br == NULL)                                    //没有相邻节点的情况
    {
        br = b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb = br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while (pb->next)   pb = pb->next;
        pb->next = b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1 = br;                 //临时相邻变量
    while (br)                        //【遍历相邻节点】
    {
        br1 = br;
        br = br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents)                       //节点集复制
{
    NEIGHBOR copynode=NULL, lastnode=NULL, head = NULL;                        //没有子节点
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(copynode->node, adjacents->node);
        copynode->next = NULL;
        if (head == NULL)
        {
            head = copynode;                                       //第1个节点
        }
        else
        {
            lastnode->next = copynode;                             //非第1个节点：建立链接，复制子节点集
        }
        lastnode = copynode;
        adjacents = adjacents->next;                               //下一个子节点
    }
    return head;                                                 //返回头节点指针
}

//3.3.2 复制路径和路径集合
PATH CopyPath(PATH path)                               //复制一条路径，返回新路径
{
    PATH tempath;
    tempath=(PATH)CopyNeighbors((NEIGHBOR)path);       //路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths)                     //复制路径集合
{
    PATHS copynode=NULL, lastnode=NULL, head = NULL;
    while (paths)                                 //路径集合不为空
    {
        copynode = (PATHS)malloc(sizeof(Paths));   //路径节点
        copynode->path = CopyPath(paths->path);    //复制一条路径
        copynode->next = NULL;                     //复制路径初始化
        if (head == NULL)                           //第1条路径
        {
            head = copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next = copynode;
        }
        lastnode = copynode;                       //加入路径集合
        paths = paths->next;
    }
    return head;
}

//3.3.3 节点加入路径
PATH Add_A_Node_To_Path(NODE node,PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p=(NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    Set(p->node,node);                        //等价，赋值
    if(path==NULL)                            //第1个节点
    {
        p->next=NULL;
    }
    else                                      //非第1个节点
    {
        p->next=path;                         //加入到路径头部
    }
    path=p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//3.3.6 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack)              //回收栈空间
{
    stack=(STACK)ClearNeighbors((NEIGHBOR)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path=(PATH)ClearNeighbors((NEIGHBOR)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths)               //回收路径集合空间
{
    PATHS paths1=paths;
    while(paths)                              //所有路径
    {
        paths1=paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths=paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//3.3.9 路径倒叙与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num = 0, i;
    NODE* nodes;
    PATH p = path;
    while (p)                                //统计路径节点的个数
    {
        p = p->next;
        num++;
    }
    nodes = (NODE*)malloc(num * sizeof(NODE)); //开辟一维数组
    for (i = 0, p = path; p; p = p->next, i++)         //读取路径节点置于数组中
    {
        Set(nodes[i], p->node);
    }
    for (i = num - 1, p = path; p; p = p->next, i--)     //数组数据倒序置于路径中
    {
        Set(p->node, nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node,PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p=path;
    STATUS flag=FALSE;                                    //节点是否在路径中的标识
    while(p)
    {
        if(equal(node,p->node)!=0)                           //node在路径中
        {
            flag=TRUE;
            break;
        }
        else                                              //node不在路径中
        {
            p=p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.5.1 给定节点的子图
GRAPH GetSubGraph(GRAPH graph,NODE node)                         //由给定节点获取所有子节点（子图），即子图指针
{
    GRAPH subgraph=graph; 
    while(subgraph)                                              //遍历图节点
    {
        if(equal(subgraph->node.node,node)==0)   break;         //找到图节点
        //if(Equal(subgraph->node.node,node,EqualFun)==0) break;
        else subgraph=subgraph->next;
    }
    return subgraph;                                             //得到子图
}


//3.6.1 判断节点的存在性
STATUS IsInAdjacents(NODE node,NEIGHBOR adjacents)   //判断节点是否在节点集合中
{
    PATH path=(PATH)adjacents;                       //节点集合与路径节点存储结构相同
    return IsInPath(node,path);                      //节点是否在路径中，复用函数IsInPath
}

//3.6.2  路径定位
PATH LocatePath(NODE node,PATHS paths)               //根据节点从路径集合中获取路径
{
    PATH path=NULL;                                  //路径
    while(paths)                                     //遍历路径集合
    {
        if(equal(paths->path->node,node)!=0)        //路径头节点与该节点相同
        //if(Equal(paths->path->node,node,EqualFun)==0)
        {
            path=paths->path;                        //找到路径
            break;
        }
        paths=paths->next;                            //继续查找
    }
    return path;                                      //返回路径
}

//3.6.3 删除路径
PATHS DelPathFromPaths(PATHS paths,PATH path)         //从路径集合中删除路径
{
    PATHS ps1=paths,ps2;
    if(paths==NULL||path==NULL)  return NULL;         //路径与路径集合不存在
    while(ps1->path!=path)                            //在路径集合中查找路径
    {
        ps2=ps1;
        ps1=ps1->next;
    }
    if(ps1!=NULL)                                     //找到路径
    {
        if(paths=ps1)                                 //路径在路径集合的头部
        {
            paths=ps1->next;
        }
        else                                          //路径不在路径集合中
        {
            ps2=ps1->next;
        }
    }
    ClearPath(ps1->path);                             //清空（删除）路径
    return paths;                                     //得到路径集合
}

//3.6.4 路径追加
PATHS Add_A_Path_To_Paths_BFS(PATH path,PATHS paths)  //将路径追加到路径集合中形成扩展的路径集合
{
    PATH copypath;                 
    PATHS ps=NULL,p;
    if(path==NULL)  return paths;                     //路径不存在，无须追加
    copypath=CopyPath(path);                          //复制路径
    ps=(PATHS)malloc(sizeof(Paths));                  //生成路径集合中的节点
    ps->path=copypath;
    ps->next=NULL;
    if(paths==NULL)                                   //路径集合为空
    {
        paths=ps;                                     //路径集合只有刚加入的路径
    }
    else                                              //路径集合不为空
    {
        p=paths;                                      //路径加入路径集合的尾部
        while(p->next)  p=p->next;
        p->next=ps;
    }
    return paths;                                     //得到路径集合
}

//3.6.5 生成路径集合
PATHS FormPaths(NEIGHBOR adjacents,PATH path)         //将节点集合中的每个节点分别加入路径
{
    PATH pt;
    PATHS paths=NULL;                                 //初始化路径集合
    while(adjacents)
    {
        pt=CopyPath(path);                            //复制路径
        pt=Add_A_Node_To_Path(adjacents->node,pt);    //在路径中加入节点，形成新路径
        paths=Add_A_Path_To_Paths_BFS(pt,paths);      //新路径加入路径集合
        adjacents=adjacents->next;                    //下一个节点
    }
    return paths;                                     //得到路径集合
}

//3.6.6 合并路径集合                                   
PATHS UnionPaths(PATHS paths1,PATHS paths)            //路径集合合并，形成新的路径集合
{
    PATHS ps=paths1;                                  //路径集合
    while(paths)                                      //路径集合不为空（所有路径）
    {
        ps=Add_A_Path_To_Paths_BFS(paths->path,ps);   //加入一条路径到路径集合中
        paths=paths->next;                            //下一条路径
    }
    return ps;                                        //合并后的路径集合
}

//3.6.7 合并节点集
NEIGHBOR UnionAdjacents(NEIGHBOR adjacents,NEIGHBOR alladjacents)     //节点集合合并【形成总节点集合】
{
    while(adjacents)                                                  //所有节点（节点集合不为空）
    {
        if(IsInAdjacents(adjacents->node,alladjacents)==FALSE)        //节点不在节点集合中
        {
            alladjacents=Add_A_Adjacents(alladjacents,adjacents->node);//加入节点
        }
        adjacents=adjacents->next;                                    //下一个节点
    }
    return alladjacents;                                              //合并后集合
}

//3.6.8 相差节点集
NEIGHBOR DiffAdjancents(NEIGHBOR adjacents,NEIGHBOR alladjacents)     //节点集合合并【将不在总结点集合中的点加入差节点集合】
{
    NEIGHBOR minusadjacents=NULL;                                     //新节点集合【差节点集合】
    while(adjacents)                                                  //所有节点
    {
        if(IsInAdjacents(adjacents->node,alladjacents)==FALSE)//bug:
        {
            minusadjacents=Add_A_Adjacents(minusadjacents,adjacents->node);
        }
        adjacents=adjacents->next;                                    //下一个节点
    }
    return minusadjacents;                                            //节点集合的差集
}

//3.7.3 九宫格的空格交换
STATUS Locate(NODE node, int* hori, int* vert, int zero)
{
    int i, j;
    STATUS flag = FALSE;
    for (i = 0; i < MAXSIZE; i++)
    {
        for (j = 0; j < MAXSIZE; j++)
        {
            if (node[i][j] == zero)
            {
                *hori = i;
                *vert = j;
                flag = TRUE;
                break;
            }
        }
        if (flag == TRUE)   break;
    }
    return flag;
}

void Exchange(NODE node, int hori1, int vert1, int hori2, int vert2)
{
    int tempnode;
    tempnode = node[hori1][vert1];
    node[hori1][vert1] = node[hori2][vert2];
    node[hori2][vert2] = tempnode;
}

//3.7.4 相邻节点集合的生成
NEIGHBOR ExpandNodes(NODE node, int zero)
{
    NEIGHBOR adjacents = NULL;
    int h, v;
    NODE tempnode;
    if (!Locate(node, &h, &v, zero))     return adjacents;
    if (h == 0 && v == 0)                                       //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h + 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 0 && v == 2)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h, v - 1);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 0)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 1)                                  //空格位置
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 1 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h + 1, v);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 0)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 1)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v + 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    else if (h == 2 && v == 2)
    {
        Set(tempnode, node);                     //对九宫格的节点赋值
        Exchange(tempnode, h, v, h - 1, v);                    //交换位置
        adjacents = Add_A_Adjacents(adjacents, tempnode);   //收集新的节点
        Set(tempnode, node);
        Exchange(tempnode, h, v, h, v - 1);
        adjacents = Add_A_Adjacents(adjacents, tempnode);
    }
    return adjacents;
}

//3.7.5 长度计算
long int LengthOfPath(PATH path)
{
    long int count=1;
    while(path!=NULL)
    {
        path = path->next;
        count++;
    }
    return count;
}

//3.9.1 广度优先子图搜索
STATUS SearchSubGraphBFSRe(NODE current,NODE end,PATH *path1,PATH *searchpath,NEIGHBOR *alladjacents1,PATHS *allpaths,int zero)
{
    NEIGHBOR adjacents;
    NEIGHBOR alladjacents=*alladjacents1;
    STATUS flag=FALSE;
    PATH path=NULL,locpath;
    PATHS paths=*allpaths;
    if(equal(current,end)==TRUE)
    {
        flag=TRUE;
        *path1=Add_A_Node_To_Path(current,NULL);
    }
    else if(IsInPath(current,*searchpath)==FALSE)
    {
        *searchpath=Add_A_Node_To_Path(current,*searchpath);
        adjacents=ExpandNodes(current,zero);
        adjacents=DiffAdjancents(adjacents,*searchpath);
        if(*allpaths==NULL)
        {
            path=Add_A_Node_To_Path(current,NULL);
            paths=FormPaths(adjacents,path);
            *allpaths=UnionPaths(*allpaths,paths);
        }
        else
        {
            locpath=LocatePath(current,*allpaths);
            path=CopyPath(locpath);
            *allpaths=DelPathFromPaths(*allpaths,locpath);
            paths=FormPaths(adjacents,path);
            *allpaths=UnionPaths(*allpaths,paths);
        }
        ClearPath(path);
        ClearPaths(paths);
        *alladjacents1=UnionAdjacents(adjacents,*alladjacents1);
        alladjacents=*alladjacents1;
        while(alladjacents)
        {
            if(IsInPath(alladjacents->node,*searchpath)==FALSE)
            {
                flag=SearchSubGraphBFSRe(alladjacents->node,end,path1,searchpath,alladjacents1,allpaths,zero);
                if(flag==TRUE)
                {
                    *path1=LocatePath(end,*allpaths);
                    break;
                }
            }
            alladjacents=alladjacents->next;
        }
    }
    return flag;
}

//3.9.2 递归路径求解
STATUS SearchPathBFSRe(NODE start,NODE end,PATH *path,int zero)
//判断节点是否在图中，广度优先搜索，生成路径【给定初始节点和目标节点得到求解路径】
{
    STATUS flag=FALSE;                                           //目标是否已存在标识
    PATH searchpath=NULL;                                        //搜索路径，表示已判断过的路径
    NEIGHBOR alladjacents=NULL;                                  //所有相邻节点（队列）
    PATHS allpaths=NULL;                                         //求解路径集合
    flag=SearchSubGraphBFSRe(start,end,path,&searchpath,&alladjacents,&allpaths,zero);
    //搜索
    if(flag==TRUE) searchpath=Add_A_Node_To_Path(end,searchpath); //若路径存在，则加入初始节点
    RevPath(searchpath);                                          //搜索路径倒序
    printf("Search Path=");                                       //显示搜索路径
    PriPath(searchpath);
    RevPath(*path);                                               //求解路径倒序
    ClearPath(searchpath);                                        //清空搜索路径
    ClearNeighbors(alladjacents);                                 //清空所有相邻节点集合
    return flag;                                                  //路径的存在性
}

//3.8.M 主程序（DFS递归）
int main()
{
    STACK stack = NULL;
    PATH path = NULL;
    STATUS flag;
    //NODE start={{2,8,3},{1,0,4},{7,6,5}},end={{1,2,3},{8,0,4},{7,6,5}};
    NODE start={{1,2,3},{8,4,0},{7,6,5}}, end={{1,2,3},{8,0,4},{7,6,5}};
    printf("Search from:\n");
    PriNode(start);
    printf("to:\n");
    PriNode(end);
    flag = SearchPathBFSRe(start, end, &path, ZERO);
    printf("Path:\n");
    RevPath(path);
    PriPath(path);
    printf("\nStep=%ld,Status=%d\n", LengthOfPath(path) - 1, flag);
    printf("=============\n");
    ClearPath(path);
    return 0;
}